package com.hyb.algorithm.data.struct.stack;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: huyanbing
 * @Date: 2021/9/5 10:16 上午
 *
 * 496. 下一个更大元素 I
 * https://leetcode-cn.com/problems/next-greater-element-i/
 *
 */
public class NextGreaterElement2 {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        int len1=nums1.length;
        int len2=nums2.length;

        int[] res=new int[len1];
        if(len1<=0){
            return res;
        }


        Stack<Integer> stack=new Stack<Integer>();

        Map<Integer,Integer> resMap=new HashMap<>();

        for(int i=len2-1;i>=0;i--){

            while(!stack.isEmpty()&&nums2[i]>=stack.lastElement()){
                stack.pop();
            }

            int ret=stack.isEmpty()?-1:stack.lastElement();
            resMap.put(nums2[i],ret);
            stack.push(nums2[i]);
        }

        for(int i=0;i<len1;i++){
            res[i]=resMap.getOrDefault(nums1[i],-1);
        }

        return res;

    }
}
